/*
给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示
输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

输出:  [1,2,4,7,5,3,6,8,9]
'之'字型打印

思路: A和B两个点从左上角出发，A点向右走，到头了向下运动，B点向下走，到头了向右走，他俩总能构成一条对角线
按照一定方向打印对角线即可。
 */
const UP = true

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var findDiagonalOrder = function (matrix) {
  let rA = 0
  let cA = 0
  let rB = 0
  let cB = 0
  let direction = UP
  const rows = matrix.length
  const cols = matrix[0].length
  const result = []
  // A点向下运动到最后一行后了
  while (rA !== rows) {
    const ret = printDiagonal(matrix, rA, cA, rB, cB, direction)
    result.push(...ret)
    rA = cA === cols - 1 ? rA + 1 : rA // A点向右移动，直到最后一列后开始向下运动
    cA = cA === cols - 1 ? cA : cA + 1 // A点一直往右移动，直到最后一列
    cB = rB === rows - 1 ? cB + 1 : cB // B点向下移动，直到最后一行后开始向右运动
    rB = rB === rows - 1 ? rB : rB + 1 // B点开始向下移动，直到最后一行
    direction = !direction
  }
  return result
}

/**
 *
 * @param {number[][]} matrix
 * @param {number} rA
 * @param {number} cA
 * @param {number} rB
 * @param {number} cB
 * @param {boolean} direction
 */
function printDiagonal (matrix, rA, cA, rB, cB, direction) {
  const ret = []
  while (rB >= rA) {
    if (direction) {
      // 上
      ret.push(matrix[rB--][cB++])
    } else {
      // 下
      ret.push(matrix[rA++][cA--])
    }
  }
  return ret
}

const matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]

findDiagonalOrder(matrix)
